/*
 * @lc app=leetcode.cn id=229 lang=typescript
 *
 * [229] 求众数 II
 */

// @lc code=start
function majorityElement(nums: number[]): number[] {
  // 出现次数最多的数字和数量
  const a = [0, 0];
  // 出现次数次多的数字和数量
  const b = [0, 0];

  for (const x of nums) {
    if (x === a[0] && a[1]) {
      a[1]++;
    } else if (x === b[0] && b[1]) {
      b[1]++;
    } else if (a[1] === 0) {
      a[0] = x;
      a[1] = 1;
    } else if (b[1] === 0) {
      b[0] = x;
      b[1] = 1;
    } else {
      a[1]--;
      b[1]--;
    }
  }

  // 重置计数，然后统计2个数字的具体出现次数
  a[1] = b[1] = 0;
  for (const x of nums) {
    if (x === a[0]) {
      a[1]++;
    } else if (x === b[0]) {
      b[1]++;
    }
  }

  const ans = [];
  const n = nums.length;
  // 出现次数超过1/3的数字放入答案
  if (a[1] * 3 > n) ans.push(a[0]);
  if (b[1] * 3 > n) ans.push(b[0]);

  return ans;
}
// @lc code=end
